package com.lizk.path;

import com.google.common.collect.Lists;
import com.lizk.graph.weight.Edge;
import com.lizk.graph.weight.WeightGraph;
import com.lizk.heap.IndexMinHeap;

import java.util.List;

/**
 * @author lizhikui
 * @date 2020/3/1 0:09
 */
public class Dijkstra {

    IndexMinHeap<Integer> heap;
    Node4ShortPath[] node;

    public void disjkstra(WeightGraph<Edge<Integer>> graph,int initNodeIndex){

        heap = new IndexMinHeap<>(graph.size());

        node = new Node4ShortPath[graph.size()];

        heap.insert(initNodeIndex,0);

        node[initNodeIndex] = new Node4ShortPath(new Edge<>(initNodeIndex,initNodeIndex,0),false,0,initNodeIndex);

        while (!heap.isEmpty()){
            int index = heap.extractMinIndex();
            node[index].setVisit(true);

            graph.iterator(index);
            while (graph.hasNext()){
                Edge<Integer> tmpEdge = graph.next();
                Node4ShortPath toNode = node[tmpEdge.getTo()];
                Node4ShortPath fromNode = node[tmpEdge.getFrom()];
                Integer weight = tmpEdge.getWeight();

                if (fromNode == null)
                    return;

                if (toNode == null){
                    toNode = new Node4ShortPath(tmpEdge,false,Integer.MAX_VALUE,tmpEdge.getTo());
                }

                //松弛操作,
                //initNode:原点
                //currNode:当前节点
                //lastNode:前一个节点
                //path(initNode->currNode):原点到当前节点的最短路径【这个最短路径只是当前访问路径中暂时最短的长度】
                //path(lastNode->currNode):前一个节点到当前节点的权值【这个就是当前节点的权值】
                //path(initNode->lastNode):原点到前一个节点的最短路径【这个是已经确定的最短路径长度】

                //当 path(initNode->lastNode) +  path(lastNode->currNode) < path(initNode->currNode)的时候
                //需要做松弛操作,当前节点的临时最短长度变为path(initNode->lastNode) +  path(lastNode->currNode),访问到当前节点的最后一个边变成了,
                //path(lastNode->currNode)对应的边
                if (!toNode.isVisit() || fromNode.getMinDistance() + weight < toNode.getMinDistance()){
                    toNode.setMinDistance(fromNode.getMinDistance() + weight);
                    toNode.setVisit(true);
                    toNode.setEdge(tmpEdge);
                    if (heap.contain(toNode.getNodeIndex())){
                        heap.change(toNode.getNodeIndex(),toNode.getMinDistance());
                    }else{
                        heap.insert(toNode.getNodeIndex(),toNode.getMinDistance());
                    }
                    node[tmpEdge.getTo()] = toNode;
                }
            }
        }
    }

    public void printPath(int toIndex){

        int tmpFromIndex = toIndex;

        int tmpToIndex = -1;

        List<Node4ShortPath> list = Lists.newArrayList();


        while (tmpFromIndex != tmpToIndex){
            Node4ShortPath node4ShortPath = node[tmpFromIndex];
            list.add(node4ShortPath);


            tmpFromIndex = node4ShortPath.getEdge().getFrom();
            tmpToIndex = node4ShortPath.getEdge().getTo();
        }

        List<Node4ShortPath> reverse = Lists.reverse(list);
        boolean notFirst = false;
        for (Node4ShortPath n:reverse){
            if (notFirst){
                System.out.print("->");
            }else{
                notFirst = true;
            }
            System.out.print(n.getEdge().getTo());
        }
        System.out.println();
    }
}
